package 每日一题;

/**
 * 1234. 替换子串得到平衡字符串
 * 有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
 *
 * 假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
 *
 *
 *
 * 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
 *
 * 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
 *
 * 请返回待替换子串的最小可能长度。
 *
 * 如果原字符串自身就是一个平衡字符串，则返回 0。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "QWER"
 * 输出：0
 * 解释：s 已经是平衡的了。
 * 示例 2：
 *
 * 输入：s = "QQWE"
 * 输出：1
 * 解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。
 * 示例 3：
 *
 * 输入：s = "QQQW"
 * 输出：2
 * 解释：我们可以把前面的 "QQ" 替换成 "ER"。
 * 示例 4：
 *
 * 输入：s = "QQQQ"
 * 输出：3
 * 解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 10^5
 * s.length 是 4 的倍数
 * s 中只含有 'Q', 'W', 'E', 'R' 四种字符
 * 通过次数7,596提交次数21,538
 * https://leetcode.cn/problems/replace-the-substring-for-balanced-string/
 */
public class D220718_T1234 {
    public static int balancedString(String s) {
        int ans = s.length();
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'A'] += 1;
        }

        int balance = s.length() / 4;

        int targetQ;
        int targetW;
        int targetE;
        int targetR;

        targetQ = Math.max(count['Q' - 'A'] - balance, 0);
        targetW = Math.max(count['W' - 'A'] - balance, 0);
        targetE = Math.max(count['E' - 'A'] - balance, 0);
        targetR = Math.max(count['R' - 'A'] - balance, 0);


        //滑动窗口 右指针先向右 直到包含所有的多余的字符 左指针再向右缩小范围

        if (targetQ + targetE + targetW + targetR == 0) {
            return 0;
        }

        int[] cur = new int[26];
        int l = 0;
        int r = 0;
        while (r < s.length()) {
            cur[s.charAt(r) - 'A']++; //统计数量
            while (l <= r && cur['Q' - 'A'] >= targetQ && cur['W' - 'A'] >= targetW && cur['E' - 'A'] >= targetE && cur['R' - 'A'] >= targetR) {
                ans = Math.min(ans, r - l + 1);
                cur[s.charAt(l) - 'A']--; //窗口左侧滑动
                l++; //左指针右移
            }
            r++; //右指针 右移
        }

        return ans;


    }

    public static void main(String[] args) {
        System.out.println(balancedString("QQWE"));
    }
}
